//
// 霍夫曼编码
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**思路：用一个有序链表（从大到小）来保存节点，然后通过链表来构造霍夫曼树, 再由霍夫曼树得到霍夫曼编码**/

typedef struct huffman_tree_node
{
    int weight;                                     //权重
    char c;                                         //字符 非叶子节点为0
    struct huffman_tree_node *nextHuffmanTreeNode;  //链表下一个节点
    struct huffman_tree_node *leftHuffmanTreeNode;  //左节点
    struct huffman_tree_node *rightHuffmanTreeNode; //右节点
} HuffmanTreeNode;                                  //霍夫曼树节点

typedef struct huffman_code
{
    char *s;   //编码 如  010， 00， ....
    int len;   //编码长度
    char c;    //字符
} HuffmanCode; //霍夫曼编码（可以用来保存结果）

/**
 * 创建一个节点
 * @param c  字符
 * @param weight 权重
 * @return
 */
HuffmanTreeNode *createHuffmanTreeNode(char c, int weight)
{
    HuffmanTreeNode *node = (HuffmanTreeNode *)calloc(1, sizeof(HuffmanTreeNode));
    node->c = c;
    node->weight = weight;
    node->nextHuffmanTreeNode = NULL;
    node->leftHuffmanTreeNode = NULL;
    node->rightHuffmanTreeNode = NULL;
    return node;
}

/**
 * [insert 插入节点到有序链表中] 从大到小
 * @param  h [头节点指针]
 * @param  s [要插入的节点]
 * @return   [头节点]
 */
static HuffmanTreeNode *insert(HuffmanTreeNode *h, HuffmanTreeNode *s)
{
    if (h == NULL)
    {             //插入第一个节点时 没有头节点
        return s; // s作为头节点
    }
    if (s->weight > h->weight)
    {
        s->nextHuffmanTreeNode = h; // s作为头节点
        return s;
    }

    HuffmanTreeNode *tempHuffmanTreeNode = h;                  //中间变量 用于遍历
    HuffmanTreeNode *preHuffmanTreeNode = tempHuffmanTreeNode; //中间变量的前一个节点
    while (tempHuffmanTreeNode != NULL)
    {
        if (s->weight < tempHuffmanTreeNode->weight)
        { //要插入的节点的权重比当前节点小
            preHuffmanTreeNode = tempHuffmanTreeNode;
            tempHuffmanTreeNode = tempHuffmanTreeNode->nextHuffmanTreeNode;
            continue;
        }
        //插入到中间
        preHuffmanTreeNode->nextHuffmanTreeNode = s;
        s->nextHuffmanTreeNode = tempHuffmanTreeNode;
        break;
    }
    if (tempHuffmanTreeNode == NULL)
    { //插入的节点比已有的节点都小
        preHuffmanTreeNode->nextHuffmanTreeNode = s;
    }
    return h;
}

/**
 * 移除最后一个节点（最小的那个） 并返回
 * @param node
 * @return
 */
HuffmanTreeNode *removeLastHuffmanTreeNode(HuffmanTreeNode *h)
{
    HuffmanTreeNode *tempHuffmanTreeNode = h;                  //中间变量 用于遍历
    HuffmanTreeNode *preHuffmanTreeNode = tempHuffmanTreeNode; //中间变量的前一个节点
    while (tempHuffmanTreeNode->nextHuffmanTreeNode != NULL)
    {
        preHuffmanTreeNode = tempHuffmanTreeNode;
        tempHuffmanTreeNode = tempHuffmanTreeNode->nextHuffmanTreeNode;
    }
    preHuffmanTreeNode->nextHuffmanTreeNode = NULL;
    return tempHuffmanTreeNode;
}

/**
 * 链表转霍夫曼树
 * @param head
 * @return
 */
HuffmanTreeNode *createTree(HuffmanTreeNode *head)
{
    if (head == NULL)
    {
        return NULL;
    }
    while (1)
    {
        //获取最小的两个节点
        HuffmanTreeNode *node1 = removeLastHuffmanTreeNode(head);
        if (node1 == head)
        { //只有一个节点了 完成
            return node1;
        }
        HuffmanTreeNode *node2 = removeLastHuffmanTreeNode(head);
        if (node2 == head)
        {                //最后一个节点
            head = NULL; //头节点置为NULL
        }
        //创建一个新的节点
        HuffmanTreeNode *newNode = createHuffmanTreeNode(0, node1->weight + node2->weight);
        //设置左节点
        newNode->leftHuffmanTreeNode = node1->weight <= node2->weight ? node1 : node2;
        //设置右节点
        newNode->rightHuffmanTreeNode = node1->weight <= node2->weight ? node2 : node1;
        //新节点插入到链表中，再次循环 直到链表中只有一个节点
        head = insert(head, newNode);
    }
}

/**
 * 字符串拷贝
 * @param s
 * @param len
 * @param dest
 */
void str_copy(char *s, int len, char *dest)
{
    for (int i = 0; i < len; i++)
    {
        dest[i] = s[i];
    }
}

/**
 * 霍夫曼编码
 * @param node 节点
 * @param s 编码的字符串 如 001,00,01...
 * @param len 编码字符串的长度
 */
void showCode(HuffmanTreeNode *node, char *s, int len)
{
    if (node->c != 0)
    { //到叶子节点了
        //打印编码结果（或保存到结构体中）：
        printf("%c->%s\n", node->c, s);
        free(s);
        return;
    }
    //遍历左节点 编码增加一个0
    char *leftS = (char *)calloc(len + 1, sizeof(char));
    str_copy(s, len, leftS);
    leftS[len] = '0';
    showCode(node->leftHuffmanTreeNode, leftS, len + 1);

    //遍历右节点 编码增加一个1
    char *rightS = (char *)calloc(len + 1, sizeof(char));
    str_copy(s, len, rightS);
    rightS[len] = '1';
    showCode(node->rightHuffmanTreeNode, rightS, len + 1);

    free(s);
}

int main18()
{
    //创建节点
    HuffmanTreeNode *head = NULL;
    HuffmanTreeNode *node_a = createHuffmanTreeNode('A', 5);
    HuffmanTreeNode *node_b = createHuffmanTreeNode('B', 4);
    HuffmanTreeNode *node_c = createHuffmanTreeNode('C', 3);
    HuffmanTreeNode *node_d = createHuffmanTreeNode('D', 2);
    HuffmanTreeNode *node_e = createHuffmanTreeNode('E', 1);
    //插入到有序链表中
    head = insert(head, node_a);
    head = insert(head, node_b);
    head = insert(head, node_c);
    head = insert(head, node_d);
    head = insert(head, node_e);
    //转霍夫曼树
    HuffmanTreeNode *tree = createTree(head);
    printf("huffman encode:\n");
    //获取编码
    char *s = (char *)malloc(0);
    showCode(tree, s, 0);
}